{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Distribution of pharma\n", "\n", "## Try me\n", " [![Open In Colab](../../_static/colabs_badge.png)](https://colab.research.google.com/github/ffraile/operations-research-notebooks/blob/main/docs/source/MIP/solved/Distribution%20Problem%20Example%20(Solved).ipynb)[![Binder](../../_static/binder_badge.png)](https://mybinder.org/v2/gh/ffraile/operations-research-notebooks/main?labpath=docs%2Fsource%2FMIP%2Fsolved%2FDistribution%20Problem%20Example%20(Solved).ipynb)\n", "\n", "## Problem Definition\n", "The US Department of Energy conducts a series of experiments in two research facilities located in Hawkins (Atlanta) and Los Angeles. The department needs to supply these facilities with pharma products that are processed in two factories in Portland and Flint. The delivery costs are summarised in the following table: \n", "\n", "| Production plants | Research Facilities | Delivery costs |\n", "|----------------------|---------------------|----------------|\n", "| Portland | Los Angeles |€30 |\n", "| Portland | Hawkins | €40 |\n", "| Flint | Los Angeles | €60 |\n", "| Flint | Hawkins | €50 |\n", "\n", "The supply and demand data is provided in the table below: \n", "\n", "| Supply | Available units | Demand | Required units |\n", "|-----------|-----------------|-------------|----------------|\n", "| Portland | 200 | Los Angeles | 300 |\n", "| Flint | 600 | Hawkins | 400 |\n", "\n", "**Implement an MILP that determines how to supply the two research facilities at minimum cost.**\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Problem Model\n", "$X_{11}$ = Units delivered from Portland to Los Angeles.\n", "\n", "$X_{12}$ = Units delivered from Portland to Hawkins.\n", "\n", "$X_{21}$ = Units delivered from Flint to Los Angeles.\n", "\n", "$X_{22}$ = Units delivered from Flint to Hawkins.\n", "Objective function:\n", "\n", "Minimize $z = 30X_{11} + 40X_{12} + 60X_{21} + 50X_{22}$\n", "\n", "Constraints:\n", "\n", "\n", "$X_{11} + X_{12} \\leq 200$ Supply from Portland\n", "\n", "$X_{21} + X_{22} \\leq 600$ Supply from Flint\n", "\n", "$X_{11} + X_{21} \\geq 300$ Demand in Los Angeles\n", "\n", "$X_{12} + X_{22} \\geq 400$ Demand in Hawkins\n", "\n", "All variables are Integer and greater or equal than zero.\n", "\n", "## Solution in Python\n", "The following scripts implement the problem model and solve it using Python.\n", "\n", "### Requirements\n", "Install the following requirements first" ] }, { "cell_type": "code", "execution_count": null, "outputs": [], "source": [ "!pip install pandas\n", "!pip install pulp\n", "!pip install IPython" ], "metadata": { "collapsed": false, "pycharm": { "name": "#%%\n" } } }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [], "source": [ "import pandas as pd\n", "import pulp\n", "import numpy as np\n", "from IPython.display import display, Markdown" ] }, { "cell_type": "code", "execution_count": 14, "metadata": {}, "outputs": [], "source": [ "# Instantiate our problem class\n", "model = pulp.LpProblem(\"Cost minimising problem\", pulp.LpMinimize)" ] }, { "cell_type": "code", "execution_count": 15, "metadata": {}, "outputs": [], "source": [ "# Construct our decision variable lists\n", "supply = ['Portland', 'Flint']\n", "demand = ['Los Angeles', 'Hawkins']\n", "\n", "\n", "variables = pulp.LpVariable.dicts(\"units \",\n", " ((i, j) for i in supply for j in demand),\n", " lowBound=0,\n", " cat='Integer')\n", "\n", "#coefficients\n", "coefficients = {}\n", "coefficients['Portland', 'Los Angeles'] = 30\n", "coefficients['Portland', 'Hawkins'] = 40\n", "coefficients['Flint', 'Los Angeles'] = 60\n", "coefficients['Flint', 'Hawkins'] = 50\n", "\n", "# Objective Function\n", "model += (\n", " pulp.lpSum([\n", " coefficients[(i,j)] * variables[(i, j)]\n", " for i in supply for j in demand])\n", ")\n", "\n", "#Constraints\n", "model += pulp.lpSum([variables['Portland', j] for j in demand]) <= 200, \"Supply From Portland\"\n", "model += pulp.lpSum([variables['Flint', j] for j in demand]) <= 600, \"Supply From Flint\"\n", "\n", "model += pulp.lpSum([variables[i, 'Los Angeles'] for i in supply]) >= 300, \"Demand in Los Angeles\"\n", "model += pulp.lpSum([variables[i, 'Hawkins'] for i in supply]) >= 400, \"Demand in Hawkins\"\n" ] }, { "cell_type": "code", "execution_count": 16, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "'Optimal'" ] }, "execution_count": 16, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Solve our problem\n", "model.solve()\n", "pulp.LpStatus[model.status]" ] }, { "cell_type": "code", "execution_count": 17, "metadata": {}, "outputs": [ { "data": { "text/markdown": [ "Total cost is 32000.00 €" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/markdown": [ "The following table shows the decision variables: " ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "
\n", "\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
VariablesSolution (GRB)Reduced cost (GRB)Objective Coefficient (GRB)Objective Lower bound (GRB)Objective Upper bound (GRB)
(Portland, Los Angeles)units__('Portland',_'Los_Angeles')200.000.0030.00-Inf50.00
(Portland, Hawkins)units__('Portland',_'Hawkins')0.0020.0040.0020.00Inf
(Flint, Los Angeles)units__('Flint',_'Los_Angeles')100.000.0060.0040.00Inf
(Flint, Hawkins)units__('Flint',_'Hawkins')400.000.0050.000.0070.00
\n", "
" ], "text/plain": [ " Variables Solution (GRB) \\\n", "(Portland, Los Angeles) units__('Portland',_'Los_Angeles') 200.00 \n", "(Portland, Hawkins) units__('Portland',_'Hawkins') 0.00 \n", "(Flint, Los Angeles) units__('Flint',_'Los_Angeles') 100.00 \n", "(Flint, Hawkins) units__('Flint',_'Hawkins') 400.00 \n", "\n", " Reduced cost (GRB) Objective Coefficient (GRB) \\\n", "(Portland, Los Angeles) 0.00 30.00 \n", "(Portland, Hawkins) 20.00 40.00 \n", "(Flint, Los Angeles) 0.00 60.00 \n", "(Flint, Hawkins) 0.00 50.00 \n", "\n", " Objective Lower bound (GRB) \\\n", "(Portland, Los Angeles) -Inf \n", "(Portland, Hawkins) 20.00 \n", "(Flint, Los Angeles) 40.00 \n", "(Flint, Hawkins) 0.00 \n", "\n", " Objective Upper bound (GRB) \n", "(Portland, Los Angeles) 50.00 \n", "(Portland, Hawkins) Inf \n", "(Flint, Los Angeles) Inf \n", "(Flint, Hawkins) 70.00 " ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/markdown": [ "The following table shows the constraints: " ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "
\n", "\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
ConstraintRight Hand SideShadow PriceSlackMin RHSMax RHS
0Supply_From_Portland200.00-30.000.00100.00300.00
1Supply_From_Flint600.000.00100.00500.00Inf
2Demand_in_Los_Angeles300.0060.000.00200.00400.00
3Demand_in_Hawkins400.0050.000.00-0.00500.00
\n", "
" ], "text/plain": [ " Constraint Right Hand Side Shadow Price Slack Min RHS Max RHS\n", "0 Supply_From_Portland 200.00 -30.00 0.00 100.00 300.00\n", "1 Supply_From_Flint 600.00 0.00 100.00 500.00 Inf\n", "2 Demand_in_Los_Angeles 300.00 60.00 0.00 200.00 400.00\n", "3 Demand_in_Hawkins 400.00 50.00 0.00 -0.00 500.00" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "total_cost = pulp.value(model.objective)\n", "display(Markdown(\"Total cost is %0.2f €\"%total_cost))\n", "\n", "display(Markdown(\"The following table shows the decision variables: \"))\n", "var_df = pd.DataFrame.from_dict(variables, orient=\"index\",\n", " columns = [\"Variables\"], dtype=object)\n", "\n", "var_df[\"Solution\"] = var_df[\"Variables\"].apply(lambda item: item.varValue)\n", "display(var_df)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.7.4" }, "pycharm": { "stem_cell": { "cell_type": "raw", "source": [], "metadata": { "collapsed": false } } } }, "nbformat": 4, "nbformat_minor": 2 }